//
// Created by PC on 2024/11/3.
// https://hydro.ac/d/teddycode/p/GESP5010
// PASS
/*
 * 挑战怪物
时间限制：1.0 s
内存限制：512.0 MB
3.2.1 题面描述
小杨正在和一个怪物战斗，怪物的血量为h，只有当怪物的血量恰好为0 时小杨才能够成功击败怪物。
小杨有两种攻击怪物的方式：
物理攻击。假设当前为小杨第i次使用物理攻击，则会对怪物造成2^(i-1) 点伤害。
魔法攻击。小杨选择任意一个质数 x（ x不能超过怪物当前血量），对怪物造成 x点伤害。由于小杨并不擅长魔
法，他只能使用至多一次魔法攻击。
小杨想知道自己能否击败怪物，如果能，小杨想知道自己最少需要多少次攻击。
3.2.2 输入格式
第一行包含一个正整数t ，代表测试用例组数。
接下来是t 组测试用例。对于每组测试用例，第一行包含一个正整数h ，代表怪物血量。
3.2.3 输出格式
对于每组测试用例，如果小杨能够击败怪物，输出一个整数，代表小杨需要的最少攻击次数，如果不能击败怪物，
输出 -1。
3.2.4

样例1:
 input:
3
6
188
9999
output:
2
4
-1
对于第一组测试用例，一种可能的最优方案为，小杨先对怪物使用魔法攻击，选择质数 5造成 5点伤害，之后对怪
物使用第 1次物理攻击，造成2^(1-1) 点伤害，怪物血量恰好为0 ，小杨成功击败怪物。
子任务编号 数据点占比
        t   	h
1 	20%	<=5 	<=10
2 	20%	<=10	<=100
3 	60%	<=10	<=10^5
对于全部数据，保证有 t=[1,10],h=[1,10^5]。
 * */
//
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n = 100001;
    bool isp[n]={0};
    for (int i = 2; i < n ; ++i)
        isp[i]=1;
    for (int j = 2; j*j <= n ; ++j)
    {
        if(isp[j])
        {
            for (int i = j+j; i<=n ; i+=j)
            {
                isp[i]=0;
            }
        }
    }
    int t,h;
    cin>>t;
    while(t--)
    {
        cin >> h;
        int ret=0;  // 攻击次数
        int hurt=1; // 攻击伤害
        while (true)
        {
           if(isp[h])
           {
               ++ret;
               break;
           }
           h-=hurt;
           if(h>=0)
           {
               ++ret;
               hurt*=2;
               continue;
           }
           if(h<0)
           {
               ret=-1;
               break;
           }
           if(h==0)
               break;
        }
        cout<<ret<<endl;
    }
    return 0;
}

